Network analysis is performed in a number of different fields. For example, network analysis is relevant to telecommunications. A telecommunications network usually includes many different nodes spanning a large geographical area. When a communication such as a telephone call is initiated, the telecommunications system decides how to route the communication from the origination point to the destination point via multiple nodes. An efficient selection of nodes can accelerate and/or reduce the cost of completion of the communication. The selection of the nodes to carry the communication may be made by performing a network analysis.
With one origination point and one termination point, the network analysis is relatively straightforward. There are, however, other communications with multiple origination points and/or multiple termination points. Network analysis in such situations becomes significantly more complicated. Such network analysis is computationally intensive at least partly because there are nodes in the telecommunications network that may or may not be selected for carrying the communication.
The so-called Steiner tree problem is applicable to these types of scenarios. Solving a Steiner tree problem can produce a routing that is satisfactory, if not optimal, for completing the communication among the many nodes that may possibly be used for interconnecting the origination and termination points. The Steiner tree problem is relevant to many different types of real-world networks in addition to telecommunication networks. Unfortunately, Steiner tree problems are notoriously difficult to solve, even with appreciable computational resources.